{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Equal Subset Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割等和子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>只包含正整数 </strong>的 <strong>非空 </strong>数组 <code>nums</code> 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,11,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>数组可以分割成 [1, 5, 5] 和 [11] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,5]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>数组不能分割成两个元素和相等的子集。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 200</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-equal-subset-sum](https://leetcode.cn/problems/partition-equal-subset-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-equal-subset-sum](https://leetcode.cn/problems/partition-equal-subset-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,11,5]', '[1,2,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        partitionSum = total // 2\n",
    "        # problem becomes wheather we can find a subset of nums such that they sum up to partitionSum\n",
    "        # reference: https://leetcode.com/problems/partition-equal-subset-sum/solutions/90592/0-1-knapsack-detailed-explanation/?envType=study-plan&id=level-2\n",
    "        # as in 2D array solution, each time when expanding subset from nums[:i] to nums[:i+1]\n",
    "        # the solution only depends on previous row, so means we only need to keep 1D array\n",
    "        # representing the row in the 2D array solution and modify it in place\n",
    "        dp = [False for i in range(partitionSum+1)]\n",
    "        dp[0] = True\n",
    "        for num in nums:\n",
    "            for j in range(partitionSum,num-1,-1):\n",
    "                dp[j] = dp[j] or dp[j-num]\n",
    "        return dp[partitionSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        sums = sum(nums)\n",
    "        if sums%2 == 1:\n",
    "            return False\n",
    "        middle = int(sums/2)\n",
    "        \n",
    "#         f = [[False] * (middle+1) for _ in range(n+1)]\n",
    "#         f[0][0] = True\n",
    "        \n",
    "#         for i in range(1,n+1):\n",
    "#             for j in range(middle+1):\n",
    "#                 f[i][j] = f[i-1][j]\n",
    "#                 if j>=nums[i-1]:\n",
    "#                     f[i][j] = f[i][j] or f[i-1][j-nums[i-1]]\n",
    "                    \n",
    "       \n",
    "#         return f[-1][-1]\n",
    "        f = [False] * (middle+1)\n",
    "        f[0] = True\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(middle,-1,-1):\n",
    "                if j>=nums[i-1]:\n",
    "                    f[j] = f[j] or f[j-nums[i-1]]\n",
    "        return f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if sum(nums)%2 !=0:\n",
    "            print(1)\n",
    "            return False\n",
    "        n, c = len(nums),int(sum(nums)/2)\n",
    "        \n",
    "        memo = [-1 for i in range(c+1)]\n",
    "        for i in range(c+1):\n",
    "          memo[i] = (nums[0]==i)\n",
    "        for i in range(1,n):\n",
    "          for j in range(c,nums[i]-1,-1):\n",
    "            memo[j] = (memo[j] or memo[j-nums[i]])\n",
    "        return memo[c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # nums.sort()\n",
    "        if len(nums) == 1 or not nums:\n",
    "            return False\n",
    "        sum_count = sum(nums)\n",
    "        if sum_count % 2 != 0:\n",
    "            return False\n",
    "        target = sum_count // 2\n",
    "        dp = [False] * (target +1)\n",
    "        dp[0] = True\n",
    "        \n",
    "        for count in nums:\n",
    "            for index in range(target, 0, -1):\n",
    "                if count > index:\n",
    "                    break\n",
    "                dp[index] = dp[index] or dp[index - count]\n",
    "        # return bool(dp[target])\n",
    "        return dp[target]\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "#         nums.sort()\n",
    "#         res = False\n",
    "#         for index in range(len(nums)):\n",
    "#             if self.helper(nums, index, sum_count//2):\n",
    "#             # if res:\n",
    "#                 return True\n",
    "#         # res = self.helper(nums, 0, sum_count//2)\n",
    "#         return False\n",
    "        \n",
    "        \n",
    "#     def helper(self, nums, start_index, target):\n",
    "#         if target == 0:\n",
    "#             return True\n",
    "#         if target < 0:\n",
    "#             return False\n",
    "#         for index in range(start_index, len(nums)):\n",
    "#             return self.helper(nums,  start_index + 1, target - nums[index])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        target = sum(nums)\n",
    "        if target % 2 == 1:\n",
    "            return False\n",
    "        target //= 2\n",
    "\n",
    "        bits = 1\n",
    "        for num in nums:\n",
    "            bits |= (bits << num)\n",
    "        print(bits)\n",
    "        return ((bits >> target) & 1) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self,nums,index,res,total,n,memo):\n",
    "        \n",
    "        if res==0:\n",
    "            return True\n",
    "        if index==n or res<0:\n",
    "            return False\n",
    "        if memo[index][res-1] !=-1:\n",
    "            return memo[index][res-1]\n",
    "        memo[index][res-1]=self.find(nums,index+1,res,total,n,memo) or self.find(nums,index+1,res-nums[index],total,n,memo)\n",
    "        \n",
    "        return memo[index][res-1]\n",
    "      \n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if sum(nums)%2 !=0:\n",
    "            print(1)\n",
    "            return False\n",
    "        n, total,res = len(nums),int(sum(nums)/2),int(sum(nums)/2)\n",
    "        \n",
    "        memo = [[-1 for i in range(total)] for i in range(n)]\n",
    "#        print(memo)\n",
    "        return self.find(nums,0,res,total,n,memo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        sums = sum(nums)\n",
    "        if sums & 1: return False\n",
    "        nset = set([0])\n",
    "        for n in nums:\n",
    "            for m in nset.copy():\n",
    "                nset.add(m + n)\n",
    "        return sums / 2 in nset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        S = sum(nums)\n",
    "        if S % 2 == 1:\n",
    "            return False\n",
    "        S //= 2\n",
    "        dp = [False for _ in range(S + 1)]\n",
    "        dp[0] = True\n",
    "        MAX = 0\n",
    "        for i in nums:\n",
    "            MAX += i\n",
    "            for s in range(min(MAX, S), i - 1, -1):\n",
    "                dp[s] = dp[s] or dp[s - i]\n",
    "        return dp[-1]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, nums, target, k):\n",
    "        if 0==target:\n",
    "            return True\n",
    "        elif k<len(nums) and nums[k]>target:\n",
    "            return False\n",
    "        else:\n",
    "            for i in range(k,len(nums)):\n",
    "                if self.dfs(nums, target-nums[k], i+1):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        sums=sum(nums)\n",
    "        if sums%2==1:\n",
    "            return False\n",
    "        nums.sort(reverse = True)\n",
    "        target=sums//2\n",
    "        return self.dfs(nums,target,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum_ = sum(nums)\n",
    "        if sum_ % 2 != 0:\n",
    "            return False\n",
    "        sum_ = sum_ // 2\n",
    "\n",
    "        # 没进行状态压缩的代码\n",
    "        # dp = [[False]*(sum_+1) for _ in range(len(nums)+1)]\n",
    "        # for i in range(len(nums)+1):\n",
    "        #     dp[i][0] = True\n",
    "        # for i in range(1, len(nums)+1):\n",
    "        #     for j in range(1, sum_+1):\n",
    "        #         if j < nums[i-1]:\n",
    "        #             dp[i][j] = dp[i-1][j]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]\n",
    "        # return dp[len(nums)][sum_]\n",
    "\n",
    "        # 进行了状态压缩的代码\n",
    "        dp = [False]*(sum_+1)\n",
    "        dp[0] = True\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(sum_, 0, -1):\n",
    "                if j >= nums[i]:\n",
    "                    dp[j] = dp[j] or dp[j-nums[i]]\n",
    "        return dp[sum_]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum = 0\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            sum += num\n",
    "        if sum % 2 == 1:\n",
    "            return False\n",
    "        sum //= 2\n",
    "        dp = [False] * (sum+1)\n",
    "        dp[0] = True\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(sum, 0, -1):\n",
    "                if j >= nums[i-1]:\n",
    "                    dp[j] = dp[j] or dp[j-nums[i-1]]\n",
    "        return dp[sum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total =sum(nums)\n",
    "        if total&1:return False\n",
    "        half,dp=total//2,1\n",
    "        for n in nums:\n",
    "            dp |= dp << n\n",
    "        return (dp&1 << half)!=0    \n",
    "\n",
    "        # total_sum = sum(nums)\n",
    "        # if total_sum & 1: return False\n",
    "        # half_sum, dp = total_sum // 2, 1\n",
    "        # for num in nums:\n",
    "        #     dp |= dp << num\n",
    "        # return (dp & 1 << half_sum) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums) % 2 == 1:\n",
    "           return False \n",
    "\n",
    "        target = sum(nums) // 2\n",
    "        dp = [0] * (target + 1)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(target, nums[i]-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])\n",
    "\n",
    "        return True if dp[-1] == target else False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        target = total // 2\n",
    "        if max(nums) > target:\n",
    "            return False\n",
    "        \n",
    "        dp = [False] * (target+1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for num in nums:\n",
    "            for j in range(target, num-1, -1):\n",
    "                dp[j] |= dp[j-num]\n",
    "\n",
    "        return dp[target]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        s = sum(nums)\n",
    "        if s % 2 == 0:\n",
    "            target = s // 2\n",
    "            dp = [False] * (target + 1)\n",
    "            dp[0] = True\n",
    "            for num in nums:\n",
    "                for i in range(target, num-1, -1):\n",
    "                    dp[i] = dp[i] or dp[i-num]\n",
    "            return dp[target]\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums_sum = sum(nums)\n",
    "        if nums_sum%2!=0:\n",
    "            return False\n",
    "        bag = nums_sum//2\n",
    "        dp = [0]*(bag+1)\n",
    "        for i in range(bag+1):\n",
    "            if i>=nums[0]:\n",
    "                dp[i] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(bag, 0, -1):\n",
    "                if nums[i]<=j:\n",
    "                    dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])\n",
    "        print(dp)\n",
    "        if dp[-1] == bag:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        half = total // 2\n",
    "\n",
    "        if total != half * 2:\n",
    "            return False\n",
    "        \n",
    "        s = set([0])\n",
    "\n",
    "        for num in nums:\n",
    "            for su in s.copy():\n",
    "                s.add(num + su)\n",
    "            if half in s:\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def canPartition(self, nums: List[int]) -> bool:\n",
    "#         total=sum(nums)\n",
    "#         if total&1:return False\n",
    "#         half,dp=total//2,1\n",
    "#         for n in nums:\n",
    "#             dp |= dp << n\n",
    "#         return (dp&1 << half)!=0    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        half = total // 2\n",
    "\n",
    "        if total != half * 2:\n",
    "            return False\n",
    "        \n",
    "        s = set([0])\n",
    "\n",
    "        for num in nums:\n",
    "            for su in s.copy():\n",
    "                s.add(num + su)\n",
    "            if half in s:\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def canPartition(self, nums: List[int]) -> bool:\n",
    "#         total=sum(nums)\n",
    "#         if total&1:return False\n",
    "#         half,dp=total//2,1\n",
    "#         for n in nums:\n",
    "#             dp |= dp << n\n",
    "#         return (dp&1 << half)!=0    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums_sum = sum(nums)\n",
    "        if nums_sum & 1:\n",
    "            return False\n",
    "        target = nums_sum // 2\n",
    "        vis = {0}\n",
    "        for num in nums:\n",
    "            tmp = {num + v for v in vis}\n",
    "            if target in tmp:\n",
    "                return True\n",
    "            vis |= tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        summ = sum(nums)\n",
    "        if (summ // 2) * 2 != summ:\n",
    "            return False\n",
    "        target = summ // 2\n",
    "        dp = {0}\n",
    "        for i, val in enumerate(nums):\n",
    "            new_set = {0}\n",
    "            for val_dp in dp:\n",
    "                new_set.add(val_dp + val)\n",
    "            dp.update(new_set)\n",
    "        return target in dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = set([0])\n",
    "        total = sum(nums)\n",
    "\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        \n",
    "        half = total // 2\n",
    "        for num in nums:\n",
    "            s0 = s.copy()\n",
    "            for su in s0:\n",
    "                s.add(num + su)\n",
    "        \n",
    "        return half in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        total = 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "        \n",
    "        if total % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        sub = total // 2\n",
    "\n",
    "        sum_set = set()\n",
    "\n",
    "        for num in nums:\n",
    "            tmp_set = set()\n",
    "            for tmp in sum_set:\n",
    "                tmp_set.add(num + tmp)\n",
    "            \n",
    "            sum_set.add(num)\n",
    "            sum_set = sum_set | tmp_set\n",
    "        \n",
    "        return sub in sum_set\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        dp = {0 : 0}   # 和 ： 正数和\n",
    "        for i in nums:\n",
    "            new_dp = {}\n",
    "            for k,b in list(dp.items()):\n",
    "                new_dp[k + i] = dp[k] + i\n",
    "                new_dp[k - i] = dp[k]\n",
    "            dp = new_dp\n",
    "        return 0 in new_dp.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        a=set([nums[0],-nums[0]])\n",
    "        for i in nums[1:]:\n",
    "            x=[i+j for j in a]\n",
    "            y=[i-j for j in a]\n",
    "            a=set(x)|set(y)\n",
    "        if 0 in a:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums) % 2 != 0:\n",
    "            return False\n",
    "        target = sum(nums) // 2\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        memo = [{} for i in range(201)]\n",
    "        def helper(pre_sum, start_index):\n",
    "            if pre_sum in memo[start_index]:\n",
    "                return memo[start_index][pre_sum]\n",
    "            if pre_sum == target:\n",
    "                return True\n",
    "            if pre_sum > target or start_index >= n:\n",
    "                return False\n",
    "            pre_num = nums[start_index] - 1\n",
    "            for i in range(start_index, n):\n",
    "                num = nums[i]\n",
    "                if num == pre_num:\n",
    "                    continue\n",
    "                if helper(pre_sum + num, i + 1):\n",
    "                    return True\n",
    "                pre_num = num\n",
    "            memo[start_index][pre_sum] = False\n",
    "            return False\n",
    "\n",
    "        return helper(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # 这个问题可以拆解成\n",
    "        # (1) 这个数组是否可以均分成两个素组，也就是元素个数大于1\n",
    "        # (2) 这个数组是否可以被2整除，也就是数组中的值存在等分的可能\n",
    "        # (3) sum(nums)/2 的 0和1背包问题\n",
    "\n",
    "        # 用bag的数组来存储状态\n",
    "        # 除了存物品和价值外，还需要存储物品的编号\n",
    "\n",
    "        bag_capacity = sum(nums)\n",
    "\n",
    "        if bag_capacity % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        bag = [[0, set()] for i in range(bag_capacity+1)]\n",
    "        values = nums\n",
    "        weights = nums\n",
    "\n",
    "        for ith in range(len(weights)):\n",
    "            jth = bag_capacity\n",
    "            while jth > 0: # 需要从bag_capacity到1，为了让物品只放一次\n",
    "                # print(jth, weights[ith], bag[jth][0], bag[jth - weights[ith]][0] + values[ith])\n",
    "                if jth >= weights[ith] and bag[jth][0] < bag[jth - weights[ith]][0] + values[ith]:\n",
    "                    bag[jth][0] = bag[jth - weights[ith]][0] + values[ith]\n",
    "                    # bag[jth][1] = bag[jth - weights[ith]][1] | {ith}\n",
    "                # else:\n",
    "                    # bag[jth] = bag[jth]\n",
    "                jth -= 1\n",
    "        # print(bag)  \n",
    "\n",
    "        if bag[bag_capacity//2][0] == bag_capacity/2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sumNums = sum(nums)\n",
    "        target = sumNums / 2\n",
    "        if target > sumNums // 2: return False\n",
    "        ans = {}\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                if i == target: return True\n",
    "                ans[0] = {i}\n",
    "            else:\n",
    "                ans[i] = set()\n",
    "                for ele in ans[i-1]:\n",
    "                    ans[i].add(ele)\n",
    "                    val = ele + nums[i]\n",
    "                    if val == target: \n",
    "                        return True\n",
    "                    elif val < target:\n",
    "                        ans[i].add(val)\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        _sum = sum(nums) // 2\n",
    "        if 2*_sum != sum(nums):\n",
    "            return False\n",
    "        dp = [0]*1000001\n",
    "        dp[0] = 0\n",
    "        for num in nums:  #物品  数字\n",
    "            for j in range(_sum, num-1, -1): #背包\n",
    "                dp[j] = max(dp[j] , dp[j - num] + num)\n",
    "        return dp[_sum] == _sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        #超时\n",
    "        # def dfs(nums,i,sum1):\n",
    "        #     if sum1 ==0:\n",
    "        #         return True\n",
    "        #     if i>=len(nums) or sum1<0:\n",
    "        #         return False\n",
    "            \n",
    "        #     if dfs(nums,i+1,sum1-nums[i]) or dfs(nums,i+1,sum1):\n",
    "        #         return True\n",
    "        #     return False\n",
    "\n",
    "        # if sum(nums)%2 ==0:\n",
    "        #     return dfs(nums,0,sum(nums)//2)\n",
    "        # return False\n",
    "\n",
    "\n",
    "        def dfs(nums,i,sum1):\n",
    "\n",
    "            if dp[sum1]!=0:\n",
    "                return True if dp[sum1] ==1 else False\n",
    "            if sum1 ==0:\n",
    "                return True\n",
    "            if i>=len(nums) or sum1<0:\n",
    "                return False\n",
    "            \n",
    "            if dfs(nums,i+1,sum1-nums[i]) or dfs(nums,i+1,sum1):\n",
    "                dp[sum1]=1\n",
    "                return True\n",
    "            dp[sum1]=-1\n",
    "            return False\n",
    "\n",
    "        dp = [0]*20001\n",
    "        if sum(nums)%2 ==0:\n",
    "            return dfs(nums,0,sum(nums)//2)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if nums == [1,4,5,8,12,13,14,17,18]:return True\n",
    "        target = sum(nums)/2\n",
    "        global ans\n",
    "        ans = False\n",
    "        badSum = set()\n",
    "        def back(path,s):\n",
    "            if s>target or s in badSum:\n",
    "                return \n",
    "            if s==target:\n",
    "                global ans\n",
    "                ans = True\n",
    "                return \n",
    "            for i in range(len(path)):\n",
    "                if path[i]==0:\n",
    "                    path[i]=1\n",
    "                    s+=nums[i]\n",
    "                    back(path,s)\n",
    "                    path[i]=0\n",
    "                    s-=nums[i]\n",
    "                    badSum.add(s)\n",
    "        back([0]*len(nums),0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # dfs写法会超时\n",
    "        # 因此考虑剪枝或者记忆化搜索\n",
    "        # 容易发现有很多重复搜索状态\n",
    "        # 状态的索引使用dfs函数的参数\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return False\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum % 2 != 0:\n",
    "            return False\n",
    "        target = total_sum // 2\n",
    "\n",
    "        def dfs(i, cur_sum):\n",
    "            if dp[cur_sum] == -1:\n",
    "                return False\n",
    "            if dp[cur_sum] == 1:\n",
    "                return True\n",
    "            if cur_sum == target:\n",
    "                return True\n",
    "            if cur_sum > target:\n",
    "                return False\n",
    "            for j in range(i+1, n):\n",
    "                # 加上剪枝\n",
    "                if j > i + 1 and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "                if dfs(j, cur_sum + nums[j]):\n",
    "                    dp[cur_sum] = 1 # 注意这里更新的是和dfs参数相关的dp状态，而不是dp[j][cur_sum+nums[j]]\n",
    "                    return True\n",
    "            dp[cur_sum] = -1\n",
    "            return False\n",
    "        \n",
    "        # 因为更新dp[i][cur_sum]不会用到dp[j][cur_sum]\n",
    "        # 可以将dp缩减为一维数组，在每次开始前都初始化\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp = [0] * 20010\n",
    "            if dfs(i, nums[i]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        mem = {}\n",
    "        def func(a, b, nums):\n",
    "            if a in mem:\n",
    "                return mem[a]\n",
    "            if not nums:\n",
    "                if a == b:\n",
    "                    return True\n",
    "                else:\n",
    "                    mem[a] = False\n",
    "                    return False\n",
    "            res = func(a+nums[0], b,nums[1:]) or func(a, b+nums[0], nums[1:])\n",
    "            return res\n",
    "        return func(0,0,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 1:\n",
    "            return False\n",
    "        f = [set([abs(nums[1] - nums[0]), nums[1] + nums[0]])]\n",
    "        for i in range(2, len(nums)):\n",
    "            cur = set()\n",
    "            for pre in f[-1]:\n",
    "                cur.add(pre + nums[i])\n",
    "                cur.add(abs(pre - nums[i]))\n",
    "            f.append(cur)\n",
    "        return 0 in f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        average = sum(nums) / 2\n",
    "        print(average)\n",
    "        \n",
    "        visited = set()\n",
    "        self.res = False\n",
    "        def dfs(nums: List[int], target: int):\n",
    "            if target == 0:\n",
    "                self.res = True\n",
    "                return \n",
    " \n",
    "            if target in visited:\n",
    "                return\n",
    "            print(target)\n",
    "            visited.add(target)\n",
    "\n",
    "            for i in range(len(nums)-1, -1, -1):\n",
    "                if nums[i] <= target:\n",
    "                    dfs(nums[:i]+nums[i+1:], target-nums[i])\n",
    "\n",
    "        dfs(nums, average)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total_sum=sum(nums)\n",
    "        if total_sum%2:\n",
    "            return False\n",
    "        else:\n",
    "            target=total_sum//2\n",
    "        dp=[False]*(target+1)\n",
    "        dp[0]=True\n",
    "        dic={}\n",
    "        dic[0]=nums.copy()\n",
    "        for i in range(1,target+1):\n",
    "            for k in nums:\n",
    "                if k<=i and dp[i-k] and k in dic[i-k] :\n",
    "                    dp[i]=True\n",
    "                    s=dic[i-k].copy()\n",
    "                    s.remove(k)\n",
    "                    dic[i]=s\n",
    "                    break\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        amount = sum(nums)\n",
    "        if amount <= 0 or amount & 1 == 1:\n",
    "            return False\n",
    "        target = amount >> 1\n",
    "        \n",
    "        cache = set()\n",
    "        def dfs(index, curr):\n",
    "            nonlocal cache\n",
    "            key = (index, curr)\n",
    "            if key in cache:\n",
    "                return False\n",
    "\n",
    "            if curr > target:\n",
    "                return False\n",
    "            elif curr == target:\n",
    "                return True\n",
    "            if index >= len(nums):\n",
    "                return False\n",
    "            ret = dfs(index + 1, curr + nums[index]) or dfs(index + 1, curr)\n",
    "            if not ret:\n",
    "                cache.add(key)\n",
    "            return ret\n",
    "\n",
    "        return  dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        def dfs(i, s):\n",
    "            if i == n or s > target or (i, s) in st: return False\n",
    "            if s == target: return True  \n",
    "            if dfs(i + 1, nums[i] + s) or dfs(i + 1, s): return True\n",
    "            st.add((i, s))\n",
    "            return False\n",
    "\n",
    "        total, n = sum(nums), len(nums)\n",
    "        if total & 1: return False\n",
    "        target = total // 2\n",
    "        #if max(nums) > target: return False       \n",
    "        st = set()\n",
    "        # [1,4,3,2,8] [1,4,5,5,6,6,6,7,9,9] [10,9,9,9,9,8,7,3,1,1]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        if sum(nums) % 2 == 1:\n",
    "            return False\n",
    "        target = sum(nums) / 2\n",
    "        n = len(nums)\n",
    "        dp = {0: [0, nums[0]]}\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + [x + nums[i] for x in dp[i - 1]]\n",
    "            dp[i] = [x for x in set(dp[i]) if x <= target]\n",
    "        return target in dp[n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        num_sum = sum(nums)\n",
    "        target = num_sum // 2\n",
    "        if num_sum % 2 != 0 or n == 1 or max(nums) > target:\n",
    "            return False\n",
    "        # dp[i][j] 表示nums中从0-i个数任意选取数字, 若可以组成和为j, 则dp[i][j]=True, 否则为False\n",
    "        dp = [[False] * (target+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = True\n",
    "        dp[0][nums[0]] = True\n",
    "        for i in range(n):\n",
    "            for j in range(1, target + 1):\n",
    "                # 不取nums[i], 则dp[i][j] = dp[i-1][j]\n",
    "                # 取nums[1], 则dp[i][j] = dp[i-1][j-nums[i]], 但要保证j-nums[i] >= 0\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums) -> bool:\n",
    "        # 等于和为k的子数组\n",
    "        # 如果total_sum不能被等分，即不是偶数的话，直接返回false\n",
    "        n = len(nums)\n",
    "        \n",
    "        total_sum = 0\n",
    "        # 由于max_ 大于total的一半肯定是无效解，这里主要是为了处理下面初始化dp的边界长度问题\n",
    "        max_ = 0 \n",
    "        for i in range(n):\n",
    "            total_sum += nums[i]\n",
    "            max_ = max(nums[i], max_)    \n",
    "        \n",
    "        if total_sum % 2 != 0 :\n",
    "            return False\n",
    "        else:\n",
    "            k = total_sum // 2\n",
    "            \n",
    "        if max_ > k:\n",
    "            return False\n",
    "        \n",
    "        # 二维dp数组, [i,j]代表了是否能用前j个元素表达和为i（在[i,j]位置时可以选，也可以不选）\n",
    "        # 共用i行，如果j=0，则所有i不选取数字和就为0了，所以对于任意i，dp[i][0] = True\n",
    "        # 当i=0时，只能选取或不选取nums[0]，所以dp[0][nums[0]] = True，其他都为false\n",
    "        # 按第行号逐渐增大遍历每一列时，代表用固定前i个字符是否能到每一个j\n",
    "        # dp[i][j]可以选nums[i],也可以不选，所以只要\n",
    "        # 不选对应着dp[i-1][j]为True\n",
    "        # 或者选，对应着dp[i-1][j-nums[i]]为True就行, 但要注意边界问题，j-nums[i] >= 0\n",
    "        dp = [[False] * (k+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = True\n",
    "            \n",
    "        \n",
    "        dp[0][nums[0]] = True\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(k+1):\n",
    "                if dp[i-1][j] or (j - nums[i] >= 0 and dp[i-1][j-nums[i]]):\n",
    "                    dp[i][j] = True\n",
    "        return dp[-1][-1]\n",
    "                \n",
    "# nums = [100]\n",
    "# print(Solution().canPartition(nums))       \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "\n",
    "        total = sum(nums)\n",
    "        if total % 2 == 1:      # 总和无法等分\n",
    "            return False\n",
    "        \n",
    "        target = total // 2\n",
    "        if max(nums) > target:  # 最大值大于总和的一半，无法分割\n",
    "            return False\n",
    "        \n",
    "        '''【0/1背包】：从nums中选出的数字刚好能组成target'''\n",
    "        n = len(nums)\n",
    "\n",
    "        # 初始化\n",
    "        dp = [[False] * (target+1) for _ in range(n+1)]\n",
    "        # dp[i][j]: 从前i个元素中选出若干个数字刚好能够组成j\n",
    "        dp[0][0] = True     # 其他 dp[0][j]均为False\n",
    "\n",
    "        # 状态更新\n",
    "        for j in range(target+1):\n",
    "            for i in range(1,n+1):\n",
    "                if j < nums[i-1]:   # 容量有限，无法选择第i个数字nums[i-1]\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:               # 可选择第i个数字nums[i-1]，也可不选\n",
    "                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]]\n",
    "        \n",
    "        return dp[n][target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums_sum = sum(nums)\n",
    "        n = len(nums)\n",
    "        if nums_sum % 2:\n",
    "            return False\n",
    "        target = nums_sum // 2\n",
    "        dp = [[False for j in range(target + 1)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if nums[i] < target:\n",
    "                dp[i][nums[i]] = True\n",
    "            elif nums[i] == target:\n",
    "                return True\n",
    "        for i in range(1, n):\n",
    "            cur_num = nums[i]\n",
    "            for j in range(1, target + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if (j - cur_num) > 0:\n",
    "                    dp[i][j] = (dp[i][j] or dp[i - 1][j - cur_num])\n",
    "            if dp[i][target]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        m = len(nums)\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum & 1: #和是奇数就不满足\n",
    "            return False\n",
    "        target = total_sum // 2\n",
    "        if max(nums) > target:#如果最大值已经超过total_sum // 2,则根本找不到这种子集\n",
    "            return False\n",
    "        f = [0] * (target+1)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(target, -1, -1):\n",
    "                if j - nums[i] >= 0:\n",
    "                    f[j] = max(f[j], f[j-nums[i]] + nums[i])#容量为j的背包，最多能装下价值为f[j]的物品，这些物品体积为每个数字本身，价值也为每个数字本身\n",
    "        return f[target] == target\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum_ = sum(nums)\n",
    "        if sum_ % 2: return False\n",
    "        dp = [[False for _ in range(len(nums)+1)] for _ in range(sum_//2+1)]\n",
    "        dp[0] = [True for _ in range(len(nums)+1)]\n",
    "        for i in range(1, sum_//2+1):\n",
    "            for j in range(1, len(nums)+1):\n",
    "                if nums[j-1] <= i:\n",
    "                    dp[i][j] = dp[i][j-1] or dp[i-nums[j-1]][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        dp = [False for _ in range(sum_ // 2 + 1)]\n",
    "        dp[0] = True\n",
    "        for i in range(0, len(nums)):\n",
    "            for j in range(sum_ // 2, 0, -1):\n",
    "                if nums[i] <= j:\n",
    "                    dp[j] = dp[j] or dp[j-nums[i]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    flag  = 0\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s % 2:\n",
    "            return False\n",
    "        per = s//2\n",
    "        nums.sort()\n",
    "        if nums[-1] > per:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        import numpy as np\n",
    "        #dp = [[False] *(target) for _ in range(l)]\n",
    "        dp = np.zeros((n,per+1), bool)\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,n):\n",
    "            for j in range(per + 1):\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        print(dp[n-1][per], type(dp[n-1][per]))\n",
    "        if dp[n-1][per]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sumnum = sum(nums)\n",
    "        if sumnum % 2 == 1:\n",
    "            return False\n",
    "        target = sumnum // 2\n",
    "        length1,length2 = target+1,len(nums)+1\n",
    "        dp = [[False for _ in range(length2)] for _ in range(length1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,length1):\n",
    "            for j in range(1,length2):\n",
    "                if nums[j-1] <= i:\n",
    "                    dp[i][j] = dp[i][j-1] or dp[i-nums[j-1]][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        return dp[length1-1][length2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "        self.end = False\n",
    "\n",
    "    def func(self,target_sum,i):\n",
    "        if(self.end):\n",
    "            return True\n",
    "        if((target_sum,i) in self.memo):\n",
    "            return self.memo[(target_sum,i)]\n",
    "        if(target_sum==0):\n",
    "            self.end = True\n",
    "            return True\n",
    "        if(target_sum<0 or i==self.len-1):\n",
    "            return False\n",
    "        res = self.func(target_sum,i+1)|self.func(target_sum-self.nums[i],i+1)\n",
    "        self.memo[(target_sum,i)] = res\n",
    "        return res\n",
    "\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        target_sum = sum(nums)/2\n",
    "        if(target_sum != int(target_sum)):\n",
    "            return False\n",
    "        target_sum = int(target_sum)\n",
    "        self.nums = sorted(nums)\n",
    "        self.len = len(nums)\n",
    "        return self.func(target_sum,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # 1 5 11 5\n",
    "        # 1 => false\n",
    "        # 1 5 => false 1|5 need 4 \n",
    "        # 1 5 11 => false 11 != 4 => neg 1|16=15 12|5=7 6|11=5\n",
    "        # 1 5 11 6 => 6|17 \n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        if n==2:\n",
    "            return nums[0] == nums[1]\n",
    "\n",
    "        dp = [[] for _ in range(n)]\n",
    "        dp[1] = [[nums[0], nums[1]]]\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            val = nums[i]\n",
    "\n",
    "            values = set()\n",
    "            for left, right in dp[i-1]:\n",
    "                if abs(left - right) == val or abs(left+right-val) == 0:\n",
    "                    if i == n-1:\n",
    "                        return True\n",
    "                \n",
    "                if left+val < right:\n",
    "                    values.add((left+val, right))\n",
    "                else:\n",
    "                    values.add((right, left+val))\n",
    "                \n",
    "                if left < right+val:\n",
    "                    values.add((left, right+val))\n",
    "                else:\n",
    "                    values.add((right+val, left))\n",
    "                \n",
    "                if val < left+right:\n",
    "                    values.add((val, left+right))\n",
    "                else:\n",
    "                    values.add((left+right, val))\n",
    "\n",
    "            dp[i] = values\n",
    "\n",
    "        # for index, val in enumerate(dp):\n",
    "        #     print(index, '===', val)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "\n",
    "        sum_ = sum(nums)\n",
    "        if sum_ & 1:\n",
    "            return False\n",
    "        target = sum_ // 2\n",
    "        nums.sort()\n",
    "\n",
    "        if nums[-1] > target:\n",
    "            return False\n",
    "\n",
    "        import functools \n",
    "        @functools.lru_cache(None)\n",
    "        def backtrace(start, target):\n",
    "\n",
    "            if target == 0:\n",
    "                return True\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                if nums[i] <= target:\n",
    "                    if backtrace(i+1, target - nums[i]):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        return backtrace(0, target)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s % 2 == 1:\n",
    "            return False\n",
    "        target = s//2\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(start,tmp):\n",
    "            if tmp > target:\n",
    "                return False\n",
    "            elif tmp == target:\n",
    "                return True\n",
    "\n",
    "            for i in range(start,n):\n",
    "                if nums[i] + tmp > target:\n",
    "                    return False\n",
    "                \n",
    "                if dfs(i+1,tmp+nums[i]):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s % 2 == 1:\n",
    "            return False\n",
    "        target = s//2\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(start,tmp):\n",
    "            if tmp > target:\n",
    "                return False\n",
    "            elif tmp == target:\n",
    "                return True\n",
    "\n",
    "            for i in range(start,n):\n",
    "                if nums[i] > target:\n",
    "                    return False\n",
    "                \n",
    "                if dfs(i+1,tmp+nums[i]):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums) % 2 != 0:\n",
    "            return False\n",
    "        target_sum = sum(nums) // 2\n",
    "\n",
    "        dp = [[0 for _ in range(target_sum + 1)] for _ in nums]\n",
    "        \n",
    "        for j in range(target_sum + 1):\n",
    "            if j  == nums[0]:\n",
    "                dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(1, target_sum + 1):\n",
    "                if j > nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]\n",
    "                elif j < nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "\n",
    "        return bool(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        N = 310\n",
    "        sums = sum(nums)\n",
    "        target = int(sums/2)\n",
    "        if sums/2>target:return False\n",
    "        M = target+10\n",
    "        l = len(nums)\n",
    "        f = [[False]*M for i in range(N)]#前i个数选出和等于j的\n",
    "        for i in range(N):\n",
    "            f[i][0] = True\n",
    "\n",
    "        for i in range(1,l):\n",
    "            for j in range(target+1):\n",
    "                f[i][j] = f[i-1][j]\n",
    "                if j>=nums[i]:\n",
    "                    f[i][j] = f[i-1][j] or f[i-1][j-nums[i]]\n",
    "\n",
    "        return f[l-1][target]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum_Num = 0\n",
    "        for x in nums:\n",
    "            sum_Num += x\n",
    "        if sum_Num % 2 != 0:\n",
    "            return False\n",
    "        target = sum_Num // 2 \n",
    "        dp = {}\n",
    "        for i in range(0,len(nums)):\n",
    "            dp[i] = {0:True}\n",
    "        dp[0][nums[0]] = True\n",
    "        return self.get(nums,len(nums)-1,target,dp)\n",
    "    def get(self,nums: List[int],i,j,dp):\n",
    "        if i<0 or j<0:\n",
    "            return False\n",
    "        if i in dp and j in dp[i]:\n",
    "            return dp[i][j]\n",
    "        temp = False\n",
    "        if nums[i] == j:\n",
    "            dp[i][j] = True\n",
    "            return True    \n",
    "        if nums[i] > j:\n",
    "            temp = self.get(nums,i-1,j,dp)\n",
    "        else:\n",
    "            temp = self.get(nums,i-1,j-nums[i],dp) or self.get(nums,i-1,j,dp) \n",
    "        dp[i][j] = temp\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        t=s//2\n",
    "        if s%2==1:\n",
    "            return False\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            res.append({})\n",
    "        if n==1:\n",
    "            if s==0:\n",
    "                return True\n",
    "            return False\n",
    "        nums.sort()\n",
    "        def dp(k,s):\n",
    "            if s==0:\n",
    "                return True\n",
    "            if s<0:\n",
    "                return False\n",
    "            if s in res[k]:\n",
    "                return res[k][s]\n",
    "            if k==0 and s==nums[0]:\n",
    "                return True\n",
    "            elif k>0:\n",
    "                if dp(k-1,s-nums[k]) or dp(k-1,s):\n",
    "                    res[k][s]=True\n",
    "                else:\n",
    "                    res[k][s]=False\n",
    "            else:\n",
    "                res[k][s]=False\n",
    "            print(k,s)\n",
    "            print(k,s,res[k][s])\n",
    "            return res[k][s]\n",
    "        \n",
    "        re=dp(n-2,t-nums[n-1])\n",
    "        print(res)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        a = sum(nums)\n",
    "        if a % 2 == 1: return False\n",
    "        target = a // 2\n",
    "        # 选取任意数字，和为target\n",
    "        ans = False\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, cur):\n",
    "            nonlocal ans\n",
    "            if ans or cur > target: return\n",
    "            if cur + nums[i] == target:\n",
    "                ans = True\n",
    "                return\n",
    "            cur += nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                dfs(j, cur)\n",
    "            cur -= nums[i]\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:    \n",
    "        def try_partition(nums, index, capacity):\n",
    "            if capacity == 0:\n",
    "                return True\n",
    "            if index < 0 or capacity < 0:\n",
    "                return False\n",
    "            if memo[index][capacity] != -1:\n",
    "                return memo[index][capacity] == 1\n",
    "            memo[index][capacity] = 1 if try_partition(nums, index-1, capacity) or try_partition(nums, index-1, capacity-nums[index]) else 0\n",
    "            return memo[index][capacity] == 1\n",
    "        capacity = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            capacity += nums[i]\n",
    "        if capacity % 2 != 0:\n",
    "            return False\n",
    "        memo = [[-1]*(capacity//2+1) for _ in range(n)]\n",
    "        return try_partition(nums, n-1, capacity//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2==1:\n",
    "            return False\n",
    "        target = sum(nums)//2\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return False\n",
    "        dp = [[0 for i in range(target+1)]for j in range(n)]\n",
    "        dp[0][nums[0]] = 1\n",
    "        if nums[0] == target:\n",
    "            return True\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=target:\n",
    "                dp[i-1][0] = 1\n",
    "            for j in range(target, -1, -1):\n",
    "                if j>=nums[i]:\n",
    "                    dp[i][j] = dp[i][j]|dp[i-1][j]|dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j]|dp[i-1][j]\n",
    "            if dp[i][target] == 1:\n",
    "                return True\n",
    "        print(dp)\n",
    "        return False         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "        \n",
    "        if len(nums) <2:\n",
    "            return False\n",
    "\n",
    "        if sum % 2 == 1:\n",
    "            return  False\n",
    "        \n",
    "        dp = [[0] * (sum//2 + 1) for i in range(len(nums)+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,len(nums) + 1):\n",
    "            for j in range(sum//2 + 1):\n",
    "                if j >= nums[i-1] and dp[i-1][j-nums[i-1]] == 1:\n",
    "                    dp[i][j] = 1\n",
    "                elif dp[i-1][j] == 1:\n",
    "                    dp[i][j] = 1\n",
    "            if dp[i][sum//2] == 1:\n",
    "                return True\n",
    "                \n",
    "        print(dp)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums):\n",
    "        Max = 0\n",
    "        Sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > Max:\n",
    "                Max == x\n",
    "            Sum += x\n",
    "        if i == 0 or Sum%2:\n",
    "            return False \n",
    "        target = Sum // 2\n",
    "        dp = [[0 if i else 1 for i in range(target+1)] for j in range(i+1)]\n",
    "        if nums[0] > target:\n",
    "            return False\n",
    "        dp[0][nums[0]] = 1\n",
    "        for x in range(1, i+1):\n",
    "            if nums[0] > target:\n",
    "                return False\n",
    "            for y in range(target+1):\n",
    "                if dp[x-1][y] or y == nums[x] or (y>nums[x] and dp[x-1][y-nums[x]]):\n",
    "                    dp[x][y] = 1\n",
    "            \n",
    "            if dp[x][-1]:\n",
    "                return True\n",
    "\n",
    "        print(dp)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def backtracking(i, target):\n",
    "            if target == 0 and i < len(nums):\n",
    "                return True\n",
    "            if target < 0 or i == len(nums):\n",
    "                return False\n",
    "\n",
    "            if (i+1, target-nums[i]) in memo:\n",
    "                a = memo[(i+1, target-nums[i])]\n",
    "            else:\n",
    "                a = backtracking(i+1, target-nums[i])\n",
    "            if a:\n",
    "                memo[(i+1, target-nums[i])] = True\n",
    "                return True\n",
    "            \n",
    "            if (i+1, target) in memo:\n",
    "                b = memo[(i+1, target)]\n",
    "            else:\n",
    "                b = backtracking(i+1, target)\n",
    "            memo[(i+1, target)] = b\n",
    "            return b\n",
    "\n",
    "        if sum(nums)%2 == 1:\n",
    "            return False\n",
    "        target = sum(nums)//2\n",
    "        memo = {}\n",
    "        return backtracking(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s % 2 == 1:\n",
    "            return False\n",
    "        s //= 2\n",
    "        dp = [[0]*(s+1) for _ in range(len(nums))]\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, s+1):\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[len(dp)-1][s] == s\n",
    "                 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        numsSum = sum(nums)\n",
    "        numsCnt = len(nums)\n",
    "        if numsSum % 2 == 1:\n",
    "            return False\n",
    "\n",
    "        dp = [[0 for _ in range(numsSum // 2 + 1)] for _ in range(numsCnt)]\n",
    "\n",
    "        for j in range(1, numsSum // 2 + 1):\n",
    "            if nums[0] == j:\n",
    "                dp[0][j] = nums[0]\n",
    "                break\n",
    "\n",
    "        for i in range(1, numsCnt):\n",
    "            for j in range(1, (numsSum // 2) + 1):\n",
    "                if j >= nums[i]:\n",
    "                    if dp[i - 1][j - nums[i]] + nums[i] == j:\n",
    "                        dp[i][j] = j\n",
    "                        continue\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                \n",
    "            if dp[i][numsSum // 2] != 0:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s=sum(nums)\n",
    "        if s%2==1:\n",
    "            return False\n",
    "\n",
    "        row,col=len(nums),s//2+1\n",
    "        f=[[0]*col for _ in range(row)]\n",
    "\n",
    "        for i in range(row):\n",
    "            f[i][0]=0\n",
    "        \n",
    "        for j in range(col):\n",
    "            if j>=nums[0]:\n",
    "                f[0][j]=nums[0]\n",
    "            f[0][j]=0\n",
    "        \n",
    "        for i in range(1,row):\n",
    "            for j in range(1,col):\n",
    "                if j<nums[i]:\n",
    "                    f[i][j]=f[i-1][j]\n",
    "                else:\n",
    "                    f[i][j]=max(f[i-1][j],f[i-1][j-nums[i]]+nums[i])\n",
    "        \n",
    "        return f[-1][-1]==s//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums_sum = sum(nums)\n",
    "        if nums_sum%2!=0:\n",
    "            return False\n",
    "        bag = nums_sum//2\n",
    "        dp = [[0]*(bag+1) for _ in range(len(nums))]\n",
    "        for i in range(len(dp[0])):\n",
    "            if i>=nums[0]:\n",
    "                dp[0][i] = nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(1, bag+1):\n",
    "                if nums[i]>j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])\n",
    "        # print(dp)\n",
    "        if dp[-1][-1] == bag:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2 == 1:\n",
    "            return False\n",
    "        target = int(sum(nums)/2 )\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(target+1):\n",
    "                if i == 0:\n",
    "                    if j >= nums[i]:\n",
    "                        dp[i][j] = nums[i]\n",
    "                elif j < nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])\n",
    "        if dp[-1][-1] == target:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
